package library;

public class myAlgorithm {
    /*
     * 作用：交换数组内的两个值
     */
    public static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(long[] arr, int l, int r) {
        long temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(float[] arr, int l, int r) {
        float temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(double[] arr, int l, int r) {
        double temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(char[] arr, int l, int r) {
        char temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
    //作用：生成下一个排列 (数组范围[l,r])
    //返回值：
    //      1.如果有下一个排列，则返回true，并对传入的数组进行修改
    //      2.如果没有下一个排列（即最后一个排列），则返回false，并生成第一个排列
    //步骤：
    //      1.从后向前查找第一个相邻严格升序的元素对(i,j),即满足arr[i]<arr[j],此时[j,r]必然降序
    //      2.在[j,r]从后向前查找第一个满足arr[i]<arr[k]的k,
    //      3.交换arr[i]和arr[k]
    //      4.此时[j,r]必然降序，逆转[j,r],使其升序
    //      5.若步骤1中找不到符合的相邻元素对，则说明当前数组降序直接reverse数组
    //时间复杂度: O(n)  空间复杂度: O(1)

    public static boolean nextPermutation(int[] arr, int l, int r) {
        if (l >= r) return false;
        if (l < 0) l = 0;
        if (r >= arr.length) r = arr.length - 1;
        if (r == l) return false;
        int i = r - 1;
        while (i >= l && arr[i] >= arr[i + 1]) --i;
        //该数组非递增，即为最后一个排列
        if (i == l - 1) {
            for (; l < r; ++l, --r) swap(arr, l, r);
            return false;
        }
        int k = r;
        while (arr[i] >= arr[k]) --k;
        swap(arr, i, k);
        for (++i; i < r; ++i, --r) swap(arr, i, r);
        return true;
    }

    public static boolean nextPermutation(int[] arr) {
        if (arr.length <= 1) return false;
        return nextPermutation(arr, 0, arr.length - 1);
    }

    public static boolean nextPermutation(long[] arr, int l, int r) {
        if (l >= r) return false;
        if (l < 0) l = 0;
        if (r >= arr.length) r = arr.length - 1;
        if (r == l) return false;
        int i = r - 1;
        while (i >= l && arr[i] >= arr[i + 1]) --i;
        //该数组非递增，即为最后一个排列
        if (i == l - 1) {
            for (; l < r; ++l, --r) swap(arr, l, r);
            return false;
        }
        int k = r;
        while (arr[i] >= arr[k]) --k;
        swap(arr, i, k);
        for (++i; i < r; ++i, --r) swap(arr, i, r);
        return true;
    }

    public static boolean nextPermutation(long[] arr) {
        if (arr.length <= 1) return false;
        return nextPermutation(arr, 0, arr.length - 1);
    }

    public static boolean nextPermutation(char[] arr, int l, int r) {
        if (l >= r) return false;
        if (l < 0) l = 0;
        if (r >= arr.length) r = arr.length - 1;
        if (r == l) return false;
        int i = r - 1;
        while (i >= l && arr[i] >= arr[i + 1]) --i;
        //该数组非递增，即为最后一个排列
        if (i == l - 1) {
            for (; l < r; ++l, --r) swap(arr, l, r);
            return false;
        }
        int k = r;
        while (arr[i] >= arr[k]) --k;
        swap(arr, i, k);
        for (++i; i < r; ++i, --r) swap(arr, i, r);
        return true;
    }

    public static boolean nextPermutation(char[] arr) {
        if (arr.length <= 1) return false;
        return nextPermutation(arr, 0, arr.length - 1);
    }

    /*
     * 作用：数组相邻元素去除
     * 描述：将数组中相邻的相同元素去除，返回去除后的末尾地址
     */
    public static int unique(int[] arr, int l, int r) {
        if (l == r) return r;
        for (int i = l + 1; i <= r; ++i)
            if (arr[l] != arr[i]) arr[++l] = arr[i];
        return l;
    }

    public static int unique(long[] arr, int l, int r) {
        if (l == r) return r;
        for (int i = l + 1; i <= r; ++i)
            if (arr[l] != arr[i]) arr[++l] = arr[i];
        return l;
    }

    public static int unique(char[] arr, int l, int r) {
        if (l == r) return r;
        for (int i = l + 1; i <= r; ++i)
            if (arr[l] != arr[i]) arr[++l] = arr[i];
        return l;
    }

    public static int unique(int[] arr, int length) {
        if (length <= 1) return 0;
        return unique(arr, 0, length - 1);
    }

    public static int unique(long[] arr, int length) {
        if (length <= 1) return 0;
        return unique(arr, 0, length - 1);
    }

    public static int unique(char[] arr, int length) {
        if (length <= 1) return 0;
        return unique(arr, 0, length - 1);
    }

    public static int unique(int[] arr) {
        if (arr.length <= 1) return 0;
        return unique(arr, 0, arr.length - 1);
    }

    public static int unique(long[] arr) {
        if (arr.length <= 1) return 0;
        return unique(arr, 0, arr.length - 1);
    }

    public static int unique(char[] arr) {
        if (arr.length <= 1) return 0;
        return unique(arr, 0, arr.length - 1);
    }

}
